In image compression algorithms such as MPEG, JPEG, pX64(H.261) and the like, established as international standards for multimedia, frames of digitized image-dependent signal data-compressed by removing image redundancies are subjected to a block transform called discrete cosine transform (DCT). Further data-compression is achieved by entropy encoding of the quantized discrete cosine transform (DCT) of each image block, in which entropy encoding variable-length codes (VLC) descriptive of components of the DCT are selected from a coding table arranged according to the respective statistical characteristics of these components--i. e., the frequency in which various values of that DCT component are likely to occur for encoding. This is a lossless coding process separate from the quantization process. Entropy codes include the Huffman, arithmetic and universal codes. The DCT is encoded using variable-length-coding (VLC) such as Huffman coding. Each DCT block is expressed as a DC coefficient and a group of AC coefficients, the DC coefficients usually being encoded differently from the AC coefficients. Since generally the DC coefficient of each block has a high correlation with the DC coefficients of peripheral blocks, the usual procedure for coding the DC coefficient of each block is to determine its difference from the DC coefficient of the previously encoded block, which difference is then Huffman encoded to generate a one-dimensional variable-length code. The difference of the DC coefficient of the block to be initially encoded is usually determined by subtracting therefrom the median value of the available range for DC coefficients. The Huffman coding of the differential DC coefficient is done according to a code look up table selected in accordance with factors such as the type of image frame being coded. Also, the AC coefficients are converted from a multi-dimensional vector into one dimension by zigzag scanning. Replacing AC coefficients less than a threshold value with zeroes and ignoring trailing zero coefficients results in data compression, owing to the higher probability that the AC coefficient value is not "0" near the DC coefficient but is "0" far from the DC coefficient in DCT region. Then, the number of consecutive "0" and the value of coefficient not "0" are expressed in two dimensions, that is, zero-run and level, respectively. For example, the DCT coefficient arrangement, such as 30, 2, 0, 0, -8, 0, 0, 0, 9, . . . , which is achieved through zigzag scanning, is expressed as (0,30), (0,2), (2,-8) and (3,9) through the zero-run and level encoding. The zero-run and level symbols are converted to variable-length-coding (VLC) using Huffman coding according to one of second through N.sup.th code look up tables, N being an integer. The code look up table that is used is selected by a classifier for the AC coefficients, which classifier may operate in dependence on the zero-run and level symbols for the DCT block.
The Huffman coding strings follow prefix codes that signal the starts of the Huffman codes. The Huffman coding strings and their prefix codes follow an image header code that contains coded information concerning the number and type of image frame described by the following code, the position in the frame of the image blocks generating the DCT blocks being coded and the identification of the code tables used during Huffman coding. In a multimedia system the image header code is usually part of a packet header code containing a use or routing code identifying the use to which a following packet of code will be put. The complete coded description of the image comprising the components described above is transmitted by the transmitting end of the system.
At the receiving end of the multimedia system, the use or routing code in the packet header code is detected to route the packet to the image reproducing equipment, in which equipment the use or routing code enables the detection of the image header codes and the prefix codes by a host processor including coders designed for such decoding. Thereafter, a Huffman decoder is used to decode the variable-length Huffman code strings. The detection of the prefix codes provides start signals to be used to start the parsing of Huffman code strings by the Huffman decoder, and the detection of appropriate portions of the image header supplies lookup table selection codes for use by the Huffman decoder. The conventional Huffman decoders for multimedia either utilize tree searching or utilize a look-up table (LUT) stored in read-only memory (ROM) to decode the variable-length decoding. The decoding can be such as to convert the variable-length code to fixed-length code descriptions of DCT coefficients, for example. The variable-length code input for one fixed-length output word is generally composed of no more than 24 bits. Theoretically, the length of an input string for a fixed-length output word of n bits can be expressed in 2.sup.n -1 or fewer bits.
In the conventional tree search method of Huffman decoding, the size of the search memory required for code conversion can be minimized. However, the search time is relatively long due to the characteristics of tree searching. As a result, it is difficult for the tree search method to be applied to an apparatus requiring fast processing, e.g., to digital television, HDTV or the like.
Alternatively, the search time can be reduced by using a look-up table (LUT) stored in code-addressed memory for decoding variable-length codes directly. The variable-length code input is supplied to a shift register used as an input address register for LUT memory. The LUT memory address in this input address register is supplied to address decoders within the LUT memory that generate selection signals for storage elements in each addressable storage location. The LUT memory stores the decoding results for each valid variable-length code at each addressable location specified by a LUT memory address having that valid variable-length code as its leading bits. So, when a valid variable-length code provides the leading bits of a LUT memory address, that input address to the LUT memory is accepted as a valid address by the LUT memory. The LUT memory reads out the decoding result corresponding to the valid variable-length code, which decoding result is stored at the validly addressed storage location. Any input address except one in which a valid variable-length code provides the leading bits of the LUT memory address is invalid. In response to any invalid input address, the LUT memory reads out a null result that indicates the LUT memory address is invalid and is thereafter discarded. However, this simple LUT decoding method requires increased memory size, so the die area in a very-large-scale-integrated (VLSI) circuit comprising the Huffman decoder tends to be undesirably large.
These increases in memory size for simple LUT decoding arise with conventional memory layout procedures where storage locations are provided for all addresses of a fixed bit width, when that bit-width is chosen equal to the longest variable-length code. One reason for increased memory size is that the decoding results for each variable-length code are stored at a number of addressable storage locations in the LUT memory, each having a valid address, the number of those addressable storage locations increasing as the variable-length code becomes shorter.
Another reason for increased memory size with LUT decoding is that only a portion of the possible input addresses for the LUT memory are valid addresses. If conventional memory layout procedures are used, to provide a general type of memory configuration that contains storage locations for all input addresses, the storage locations associated with invalid input addresses contain only coding nulls and are wasted. Furthermore, the memory addressing decoders must decode all input addresses, whether they are valid or invalid, in order to select the variable-length decoding results only in response to the valid variable-length codes as correctly positioned in the shift register supplying memory input addresses. Accordingly, the address coding circuitry takes up appreciable space on the die.